package Offer;

import org.junit.Test;

import java.util.*;

/*

题目:
    输入一个整数数组，判断该数组是不是某 **二叉搜索树** 的后序遍历结果。
    如果是则返回 true，否则返回 false。
    假设输入的数组的任意两个数字都互不相同。

思路:
    给的条件是后序遍历序列，还有二叉排序树；让你去构造一个二叉树
    1)虽然二叉搜索树的中序遍历实际上就是升序数组，当时不同的二叉
      搜索树得到的中序序列是相同的，所以无法根据此条件确定二叉树

    2)后序遍历是 左 右 根，所以可以采用 进行划分，然后递归子树进行判断
      i标记后序序列的第一个元素，j标记最后一个元素
      从左到右，找到第一个元素值>postorder[j]，该位置为m
      [i,m-1] 左子树
      [m,j-1] 右子树
      然后递归左右子树判断

问题:
    之前由中序后序去构造二叉树的算法怎么写?

* */
public class T33_verifyPostorder {

    @Test
    public void test() {
        int[] postorder = {4, 8, 6, 12, 16, 14, 10};
        verifyPostorder(postorder);
    }

    //方法1 递归
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    /*
        时间复杂度分析：
            每调用一轮递归会减去一个结点，因此递归占用O(n);
            每轮递归（包括左、右）都会遍历所有结点，所以为O(n)
            故总的时间复杂度为O(n^2)

        空间复杂度：
            当树退化为链表的时候，递归深度达到O(n)
     */
    public boolean recur(int[] postorder, int i, int j) {
        if (i >= j) {    //比如 序列 [1,2] 这个时候往下层递归就会出现 i>j 的情况
            return true;
        }
        int p = i;

        while (postorder[p] < postorder[j]) { //找到右子树的第一个结点
            p++;
        }

        int m = p; //标记左右子树的分界

        while (postorder[p] > postorder[j]) { //遍历完右子树，主要是为了验证右子树是否合法，
            p++;
        }

        //如果p!=j 则说明该后序序列是错的
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1); //递归检查左右子树
    }

    /*
    =================================================================================================
    方法2 单调栈（相比与解法一，这个效率高很多，可能笔试有硬性要求写O(N)的。。。。）
    参考链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/di-gui-he-zhan-liang-chong-fang-shi-jie-jue-zui-ha/
        **注：我们并没有将数组反转，只是通过逆序遍历的方式
        下面提到的下标i,i+1都是对反转后的数组来说的，不要被误导了！！！
        如果采用的是后序序列逆序（根——右——左）
        1）如果序列中出现升序序列arr[i]<arr[i+1],那么arr[i+1]一定是arr[i]的右孩子
        2）如果arr[i]>arr[i+1]，那么arr[i+1]一定是arr[0]……arr[i]中某个节点的左子节点，并且这个值是大于arr[i+1]中最小的。


        对于单调栈的理解，就是倒序遍历所有节点，则第一个节点肯定是根节点，
        之后再先遍历的都是他右子树的节点，都比他大就压栈，之后再遍历就发现
        比当前节点小的就循环将栈顶出栈并赋值root节点，直到遇到最小的比它大
        的值就是它的根节点，而再继续遍历，那么遍历的就是当前这个根节点的左子
        树了，也就是说都比当前根节点要小，如果发现比当前根节点要大了，那么就
        是return false;当遍历结束没有返回false，就说明符合二叉搜索树

        这也是为什么要用逆序遍历的原因吧...

    复杂度分析：
        时间复杂度：O(N) 遍历每个结点，每个结点都会执行一次入栈出栈操作，所以时间复杂度是O(N)
        空间复杂度：O(N)最差情况下，单调栈存储所有的结点，空间复杂度为O(n)


    关于if (cur > parent) return false; 的思考
    三个前提
    1.两个数如果arr[i]<arr[i+1]，那么arr[i+1]一定是arr[i]的右孩子
    2.如果arr[i]>arr[i+1]，那么arr[i+1]一定是arr[0]……arr[i]中某个节点的左孩子，并且这个值是大于arr[i+1]中最小
    3.递增栈
    当遇到一个值a小于栈顶值时，需要找到该值的父节点b(即栈内最早压栈的且大于该值的值)
    找到该值b以后作为parent值, a为b的左孩子(a会被压入栈中)

    后续再遇到值cur，有如下情况：
    1.它是栈内某个值的左孩子,即执行while (!stack.isEmpty() && stack.peek() > cur)语句，那么该值肯定小于等于栈顶值a，(递增栈，栈顶最大)-->cur<parent <a <b;
    2.它是栈顶值a的右孩子,即不执行while (!stack.isEmpty() && stack.peek() > cur)语句，但是a是b的左孩子，因此它的孩子值也不能大于b --> cur<b(parent);
    这就是为什么该值cur无论如何也不能大于b(parent)的原因。
    * */
    public boolean verifyPostorder2(int[] postorder) {
        Deque<Integer> stack = new LinkedList<>();
        int parent = Integer.MAX_VALUE;

        //注意for循环是倒序遍历的
        for (int i = postorder.length - 1; i >= 0; i--) {
            int cur = postorder[i];

            //如果当前节点小于栈顶元素,说明当前节点是前面某个节点的左子节点(你这里按照数组反转后去理解会好一点)，我们要找到他的父节点
            while (!stack.isEmpty() && stack.peekLast() > cur)
                parent = stack.removeLast();

            if (cur > parent)   //检查树是否合法的条件就在这里
                return false;

            //入栈
            stack.addLast(cur); //当前元素是栈顶元素的右孩子，让其入栈 （无论如何当前元素都会入栈的）
        }
        return true;
    }

    public boolean verifyPostorder3(int[] postorder){
        Deque<Integer> stack = new LinkedList<>();
        int parent = Integer.MAX_VALUE;

        for (int i = postorder.length - 1; i >= 0; i--) {
            int cur = postorder[i];
            while (!stack.isEmpty() && stack.peekLast() > cur) {
                parent = stack.removeLast();
            }

            if (cur > parent) {
                return false;
            }

            stack.addLast(cur);
        }
        return true;
    }
}
